#include "Sorter.h"


Sorter::~Sorter(void)
{
	delete sorted;
}

vector<ExtentStatsAlgo*>* Sorter::sort(vector<ExtentStatsAlgo*>* extents){
	sortedExtents.clear();
	b.clear();
	high1=0; low1=99999999; high2=0; low2=99999999; high3=0; low3=99999999;

	switch (sort_type)
	{
	case 0:
		sortedExtents=*(extents);
		b=*(extents);
		merge_sort(0, extents->size()-1);
		return new vector<ExtentStatsAlgo*> (sortedExtents);
	case 1: 
		return new vector<ExtentStatsAlgo*> (*percentageSort(extents));
		
	default:
		sortedExtents=*(extents);
		b=*(extents);
		merge_sort(0, extents->size()-1);
		return new vector<ExtentStatsAlgo*> (sortedExtents);
	}
}

// sortType=1
vector<ExtentStatsAlgo*>* Sorter::percentageSort(vector<ExtentStatsAlgo*>* extents){
	map<LUNID, int> numExtents;	// for each lun, the map holds the number of extents in the list
	map<LUNID, int>::iterator lunsIter;
	vector<ExtentStatsAlgo*>::iterator extentsIter;
	vector<ExtentStatsAlgo*> ssd, fc, sata;
	LUNID lid;
	
	// sort all extent by parameter totalRM
	sortedExtents=*(extents);
	b=*(extents);
	merge_sort(0, extents->size()-1);
	extents=&sortedExtents;

	// counts how many extents there are for each lun (in the time slices receives)
	extentsIter=extents->begin();
	while(extentsIter!=extents->end()){
		lid = (*extentsIter)->getExtent()->getLun()->getM_uid();
		lunsIter=numExtents.find(lid);
		// lun already exists
		if(lunsIter!=numExtents.end()){
			(*lunsIter).second++;
		}
		// lun doesnt exist
		else{
			numExtents.insert(pair<LUNID, int> (lid,1));
		}
		extentsIter++;
	}

	// divide the extent entries to lists by devices
	map<LUNID, int> extentsSoFar;
	map<LUNID, int>::iterator soFar;
	map<LUNID, LunTotalStatistics*>::iterator liter;
	Lun* l;
	extentsIter = extents->begin();
	while(extentsIter!=extents->end()){
		// find lun
		lid = (*extentsIter)->getExtent()->getLun()->getM_uid();
		liter=luns->find(lid);
		l=(*liter).second->getLun();
		// finding out where to add the new extent to (which device list)
		soFar = extentsSoFar.find(lid);		// how many extents were already put in the lists for this lun
		if (soFar==extentsSoFar.end()){
			extentsSoFar.insert(pair<LUNID, int> (lid, 0));
			soFar = extentsSoFar.find(lid);
		}
		lunsIter = numExtents.find(lid);	// how many total extents this lun has
		if (((*soFar).second) < ((l->getSsdPercent())*(*lunsIter).second)){
			ssd.push_back(*extentsIter);
			(*soFar).second++;
		}
		else if(((*soFar).second) < (((l->getSsdPercent())+(l->getFcPercent()))*(*lunsIter).second)){
			fc.push_back(*extentsIter);
			(*soFar).second++;
		}
		else{
			sata.push_back(*extentsIter);
			(*soFar).second++;
		}
		extentsIter++;
	}

	// adding the 3 lists to one vector
	sorted->clear();
	vector<ExtentStatsAlgo*>::iterator iter;
	iter=ssd.begin();
	while(iter!=ssd.end()){
		sorted->push_back(*iter);
		iter++;
	}
	iter=fc.begin();
	while(iter!=fc.end()){
		sorted->push_back(*iter);
		iter++;
	}
	iter=sata.begin();
	while(iter!=sata.end()){
		sorted->push_back(*iter);
		iter++;
	}
	return sorted;
}

//sortType!=1
void Sorter::merge_sort(int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		merge_sort(low,mid);
		merge_sort(mid+1,high);
		merge(low,mid,high);
	}
}

void Sorter::merge(int low,int mid,int high)
{
	int h,i,j,k;
	h=low;
	i=low;
	j=mid+1;

	while((h<=mid)&&(j<=high))
	{
		if(((sortedExtents[h]->getTotalRM()+1) * sortedExtents[h]->getExtent()->getLun()->getPriority()) >= ((sortedExtents[j]->getTotalRM()+1) * sortedExtents[j]->getExtent()->getLun()->getPriority()))
		{
			b[i]=sortedExtents[h];
			h++;
		}
		else
		{
			b[i]=sortedExtents[j];
			j++;
		}
		i++;
	}
	if(h>mid)
	{
		for(k=j;k<=high;k++)
		{
		b[i]=sortedExtents[k];
		i++;
		}
	}
	else
	{
		for(k=h;k<=mid;k++)
		{
		b[i]=sortedExtents[k];
		i++;
		}
	}
	for(k=low;k<=high;k++){
		if (b[k]->getExtent()->getLun()->getPriorityGroup()==1){
			if ((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) > high1)
				high1=b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority();
			else if (((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) < low1) && (b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()>0))
				low1=(b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority());
		}
		if (b[k]->getExtent()->getLun()->getPriorityGroup()==2){
			if ((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) > high2)
				high2=b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority();
			else if (((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) < low2) && (b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()>0))
				low2=(b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority());
		}
		if (b[k]->getExtent()->getLun()->getPriorityGroup()==3){
			if ((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) > high3)
				high3=b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority();
			else if (((b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()) < low3) && (b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority()>0))
				low3=(b[k]->getTotalRM()*b[k]->getExtent()->getLun()->getPriority());
		}
		sortedExtents[k]=b[k];
	}
}